/****************************************
 *  循环双向链表逻辑
 * Created by zlj on 2024/6/25.
****************************************/
#include "DCLinkedList.h"

/**
 * 初始化
 * @param list
 */
void InitDCLinkedList(DList *list)
{
    //申请头结点空间
    DNode *s = DNODE;
    assert(s != NULL);
    //将头结点连接到管理结点
    list->first = list->last = s;
    //设置前驱指针指向（指向头结点）
    list->first->prio = list->last;
    //设置后继结点指向（指向尾结点）
    list->last->next = list->first;
    list->size = 0;
}

/**
 * 尾插
 * @param list
 * @param x
 */
void DCLinkedList_push_back(DList *list, ElemType x)
{
    //要插入的结点
    DNode *s = _buyDNode(x);
    //将插入结点与头结点连接
    s->next = list->last->next;
    s->next->prio = s;
    //将插入结点与上一尾结点连接
    s->prio = list->last;
    list->last->next = s;
    //修改双向链表管理结点的尾指针
    list->last = s;
    list->size++;
}

/**
 * 头插
 * @param list
 * @param x
 */
void DCLinkedList_push_front(DList *list, ElemType x)
{
    DNode *s = _buyDNode(x);
    //连接新插入的节点和其一个结点
    s->next = list->first->next;
    s->next->prio = s;

    s->prio = list->first;
    list->first->next = s;
    if (list->first == list->last)
        list->last = s;
    list->size++;
}

/**
 * 打印数据
 * @param list
 */
void DCLinkedList_show_list(DList *list)
{
    DNode *p = list->first->next;
    while (p != list->first)
    {
        printf("%d-->", p->data);
        p = p->next;
    }
    printf("Nul. \n");
}

/**
 * 尾删除
 * @param list
 */
void DCLinkedList_pop_back(DList *list)
{
    if (list->size == 0)
        return;
    DNode *p = list->last;
    list->last = list->last->prio;
    p->next->prio = p->prio;
    p->prio->next = p->next;
    free(p);
    list->size--;
}

/**
 * 头删除
 * @param list
 */
void DCLinkedList_pop_front(DList *list)
{
    if (list->size == 0)
        return;
    DNode *p = list->first->next;
    p->next->prio = p->prio;
    p->prio->next = p->next;
    if (list->size == 1)
    {
        list->last = list->first;
    }
    list->size--;
}

/**
 * 按值插入
 * @param list
 * @param x
 */
void DCLinkedList_insert_val(DList *list, ElemType x)
{
    DNode *p = list->first;
    while (p->next != list->last && p->next->data < x)
    {
        p = p->next;
    }
    if (p->next == list->last && p->next->data < x)
    {
        DCLinkedList_push_back(list, x);

    } else
    {
        DNode *s = _buyDNode(x);
        s->next = p->next;
        s->next->prio = s;
        s->prio = p;
        p->next = s;
        list->size++;
    }
}

/**
 * 查找值所在位置
 * @param list
 * @param x
 * @return
 */
DNode *DCLinkedList_find(DList *list, ElemType x)
{
    DNode *p = list->first->next;
    while (p != list->first && p->data != x)
    {
        p = p->next;
    }
    if (p == list->first)
        return NULL;
    return p;
}

/**
 * 有效节点长度
 * @param list
 * @return
 */
int DCLinkedList_length(DList *list)
{
    return list->size;
}

/**
 * 按值删除
 * @param list
 * @param x
 */
void DCLinkedList_delete_val(DList *list, ElemType x)
{
    if (list->size == 0)
        return;
    DNode *p = DCLinkedList_find(&list, x);
    if (p == NULL)
    {
        printf("Not found to be deleted data . \n");
        return;
    }
    if (p == list->last)
    {
        DCLinkedList_pop_back(list);
    } else
    {
        p->next->prio = p->prio;
        p->prio->next = p->next;
        free(p);
        list->size--;
    }
}

/**
 * 升序
 * @param list
 */
void DCLinkedList_sort(DList *list)
{
    if (list->size == 0 || list->size == 1)
        return;
    //拆分
    DNode *s = list->first->next;
    DNode *q = s->next;
    list->last->next = NULL;
    list->last = s;
    list->last->next = list->first;
    list->first->prio = list->last;

    while (q != NULL)
    {
        s = q;
        q = q->next;

        DNode *p = list->first;
        while (p->next != list->last && p->next->data < s->data)
        {
            p = p->next;
        }
        if (p->next == list->last && p->next->data < s->data)
        {
            //尾插入
            s->next = list->last->next;
            s->next->prio = s;
            s->prio = list->last;
            list->last->next = s;
            list->last = s;
        } else
        {
            s->next = p->next;
            s->next->prio = s;
            s->prio = p;
            p->next = s;
        }
    }
}

/**
 * 倒置
 * @param list
 */
void DCLinkedList_resver(DList *list)
{
    if (list->size == 0 || list->size == 1)
        return;
    DNode *p = list->first->next;
    DNode *q = p->next;
    list->last->next = NULL;
    list->last = p;
    list->last->next = list->first;
    list->first->prio = list->last;

    while (q != NULL)
    {
        p = q;
        q = q->next;
        //头插入
        p->next = list->first->next;
        p->next->prio = p;
        p->prio = list->first;
        list->first->next = p;
    }
}

/**
 * 清空有效结点
 * @param list
 */
void DCLinkedList_clear(DList *list)
{
    if (list->size == 0)
        return;
    DNode *p = list->first->next;
    while (p != list->first)
    {
        p->next->prio = list->first;
        list->first->next = p->next;
        free(p);
        p = list->first->next;
    }
    list->last = list->first;
    list->size = 0;
}

/**
 * 销毁
 * @param list
 */
void DCLinkedList_destory(DList *list)
{
    DCLinkedList_clear(list);
    free(list->first);
    list->first = list->last = NULL;
}

